package come.homework;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-11
 * Time: 17:10
 */
public class Test {

}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/394643202/
    //方法二迭代法，暂时不懂
class Solution {
    int post_idx;//后续结点的下标
    int[] postorder;//将形参赋值进去，方便方法递归调用
    int[] inorder;
    Map<Integer, Integer> map = new HashMap<>();//方便查找

    private TreeNode helper(int in_left, int in_right) {
        if (in_left > in_right) {
            return null;
        }
        //找出当前根节点的值，为后续map的查找分割左右子树的结点准备
        int root_val = postorder[post_idx];
        //建立一个根节点
        TreeNode root = new TreeNode(root_val);
        //根据root_val分割左右子树
        int index = map.get(root_val);
        //改变postorder数组的下标，-1
        post_idx--;
        //构造右子树
        //两者顺序不可颠倒，后序遍历就是从右子树逐渐返回根节点
        //否则会出现越界问题
        root.right = helper(index + 1, in_right);
        //构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;//初始化
        this.inorder = inorder;
        post_idx = postorder.length - 1;//根节点
        //建立哈希表
        int index = 0;//中序数组初始位置
        for (Integer val : inorder) {
            map.put(val, index++);
        }
        return helper(0, inorder.length - 1);
    }
}